#include "utils.h"

class Solution
{
public:
    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL) return;
        ListNode *mid = head, *tail = head, *p = NULL;

        // find the middle node of the list
        while(tail!=NULL && tail->next!=NULL) {
            mid = mid->next;
            tail = tail->next->next;
        }
        p = mid;
        mid = mid->next;
        p->next = NULL;

        //reverse the linked list mid
        tail = mid;
        while(tail->next != NULL) {
            p = tail->next;
            tail->next = p->next;
            p->next = mid;
            mid = p;
        }

        while(mid!=NULL) {
            p = mid;
            mid = mid->next;
            p->next = head->next;
            head->next = p;
            head = head->next->next;
        }
    }
    void reverseReorderList(ListNode *head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL) return;
        ListNode *beg = head->next, *p = NULL;
        head->next = head->next->next;
        head = head->next;
        beg->next = NULL;
        while(head->next!=NULL && head->next->next!=NULL) {
            p = head->next;
            head->next = p->next;
            head = head->next;
            p->next = beg;
            beg = p;
        }
        if (head->next != NULL) head = head->next;
        head->next = beg;
    }
};

int main(int argc, char *argv[])
{
    //int a[] = {1};
    //int a[] = {1,2};
    //int a[] = {1,2,3};
    //int a[] = {1,2,3,4,5};   
    int a[] = {1,2,3,4,5,6};   
    ListNode *head = make_list(a,sizeof(a)/sizeof(int));
    print_list(head);
    Solution ss;
    ss.reorderList(head);
    print_list(head);
    return 0;
}
